//机器分配
#include <iostream>
using namespace std;
const int MAXN=10;
const int MAXM=15;

int n,m;
int profit[MAXN+1][MAXM+1];
int maxprofit[MAXN+1][MAXM+1];//maxprofit[i][j]表示前i个公司分配j台机器的最大盈利
int choise[MAXN+1][MAXM+1];//choise[i][j]表示当前i个公司分配j台机器取得最大盈利时，第i个公司分配多少台
int output(int i,int j){
    int k=choise[i][j];
    if (i>1) output(i-1,j-k);
    cout<<i<<' '<<k<<endl;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>profit[i][j];
    
    maxprofit[0][0]=0;
    for(int j=1;j<=m;j++) {
        maxprofit[1][j]=profit[1][j];
        choise[1][j]=j;
    }

    for(int i=2;i<=n;i++)
        for(int j=1;j<=m;j++){
            maxprofit[i][j]=maxprofit[i-1][j];
            for(int k=j;k>=1;k--)//这里也可以从小到大遍历，但那样的结果与测试数据不一致。
                if (maxprofit[i-1][j-k]+profit[i][k]>maxprofit[i][j]){
                    maxprofit[i][j]=maxprofit[i-1][j-k]+profit[i][k];
                    choise[i][j]=k;
                }
        }

    
    cout<<maxprofit[n][m]<<endl;
    output(n,m);
}